Certain computing operations are known to consume significant processor resources. Depending on the application or environment in which the processing is occurring, the computing operations may create a processing bottleneck or unacceptable processing delays. Therefore, it is desirable to make the computing operations as efficient as possible and as fast as possible.
For example, computing an exponent operation, in which a relatively large number is raised to the power of another large number, is known to be computationally intensive. At least three computationally expensive actions can occur. First, it is possible that the base number, the exponent number, and the result number will not fit into any available register of the processor, causing a condition called register overflow. When a register overflow occurs, the base number, exponent number or result number must be stored in main memory. This requires the processor to use slower, memory-based operations rather than faster, register-based operations to compute the numbers.
Second, as the result number is computed, it grows rapidly in terms of length in bytes. As a result, it is often necessary to repeatedly allocate additional memory for storage of the result, as the result grows. This requires repeated use of computationally expensive memory allocation operations.
Modulo operations are also known to be computationally expensive. A modulo value is the integer remainder that results when one number (the dividend) is evenly divided by another number (the divisor). In past approaches, processor divide instructions have been used to compute a modulo. Divide instructions are known to require several processor operations that are relatively slow. Also, in past approaches, modulo computation wastes memory and other computing resources because unnecessary values are stored and maintained, such as intermediate results of the division instructions. Further, the past approaches generally involve carrying out division operations on non-significant portions of the dividend. Thus, when used in certain applications, such as high-speed networks, they can create a bottleneck.
One context in which these problems become acute is in computing key values that are used in secure data communications. The proliferation of network computing has dramatically increased the flow of information between computers. Accompanying the increased flow of information is an increased concern for providing secure communication.
Cryptography is the art and science of keeping messages secure. A message is information or data that is arranged or formatted in a particular way. In general, a message, sometimes referred to as "plaintext" or "cleartext", is encrypted or transformed using a cipher to create "ciphertext" which disguises the message in such a way as to hide its substance. In the context of cryptography, a cipher is a mathematical function. Once received by the intended recipient, the ciphertext is decrypted to convert the ciphertext back into plaintext. Ideally, ciphertext sufficiently disguises a message in such a way that even if the ciphertext is obtained by an unintended recipient, the substance of the message cannot be discerned from the ciphertext.
There are many different encryption/decryption approaches for protecting information. Several approaches are described in "Applied Cryptography", Second Edition, by Bruce Schneier. The selection of a particular encryption/decryption approach depends upon the requirements of a particular application. Some of the considerations include the types of communications to be made more secure, the particular environment parameters in which the security is to be implemented and desired level of security. An important consideration is the particular system on which a particular security scheme is to be implemented since the level of security often has a direct effect on system resources.
For example, for small applications that require only a relatively low level of security, a traditional restricted algorithm approach may be used. With a restricted algorithm approach, a group of participants agree to use a particular algorithm to encrypt and decrypt messages exchanged between the participants. Since the algorithm is maintained in secret, a relatively simple algorithm may be used. However, if the secrecy of the algorithm is compromised, then the algorithm must be changed. Keeping the algorithm secret becomes more difficult as the number of participants increases. In addition, standard algorithms can't be used since each group of participants must have their own algorithm.
To address the shortcomings of traditional restricted algorithm approaches, many contemporary cryptography approaches use a key-based algorithm. There are generally two types of key-based algorithms: symmetric and public key. The "key" forms one input to a mathematical function used to generate a ciphertext.
Public key algorithms are designed so that the key used for encryption is different than the key used for decryption. The decryption key cannot, at least not in any reasonable amount of time, be determined from the encryption key. The encryption key (public key) is typically made public so that anyone, including an eavesdropper, can use the public key to encrypt a message. However, only a specific participant in possession of the decryption key (private key) can decrypt the message. A common extension of the basic public key encryption approach is for a group of participants to publish their public keys in a database and maintain their own private keys. Participants can simply obtain the public key of the participant to whom they want to send a message from the database and use it to encrypt a message to be sent to that participant.
Most public key algorithms are used to encrypt keys, and not messages, because they can require a relatively large amount of system resources and time to encrypt entire messages, and also because public key encryption systems are vulnerable to chosen-plaintext attacks, particularly when there are relatively few possible encrypted messages.
An increasingly popular method for establishing a secure data communication channel involves key exchange in a public key cryptosystem. Two or more parties, who wish to communicate over a secure channel, exchange or make available to each other public or non-secure key values. Each party uses the other party's public key value to privately and securely compute a private key, using an agreed-upon algorithm. The parties then use their private keys in a separate encryption algorithm that is used to encrypt messages passed over the data communication channel. The private keys are also called session keys and are used to encrypt/decrypt a specified number of messages or used to encrypt/decrypt messages for a specified period of time. A typical scenario for exchanging a message between participants A and B using a public key algorithm involves the following steps:
1. B provides a public key K to A PA1 2. A generates a random session key SK, encrypts it using public key K and sends it to B PA1 3. B decrypts the message using private key K' to recover the session key SK PA1 4. Both A and B use the session key SK to encrypt their communications with each other PA1 [1] A privately computes a public key Y as: Y=G.sup.x mod P PA1 [2] B privately computes a public key Y' as: Y'=G.sup.x' mod P PA1 [3] A computes a private key Z as: Z=Y'.sup.x mod P PA1 [4] B computes a private key Z' as: Z'=Y.sup.x' mod P
This approach provides the added security of destroying the session key at the end of a session which provides stronger protection against eavesdroppers since each session key has a limited life.
A well known public key exchange method is the Diffie-Hellman method described in U.S. Pat. No. 4,200,770 issued on Apr. 29, 1980 and entitled "Cryptographic Apparatus and Method." According to the Diffie-Hellman method, two participants, A and B, who wish to communicate securely, each select random large numbers x and x' that are kept secret. A and B also agree (publicly) upon a base number G and a large prime number P. A and B exchange the values of G and P over a non-secure channel or publish them in a database that both can access. Then A and B each privately compute public keys Y and Y', respectively, as follows:
A and B then exchange or publish their respective public keys Y and Y' and determine private keys Z and Z' as follows:
Thus, A's private key is a function of its own private random number (x) and the public key (Y') determined by A. As it turns out, Z is equal to Z' based upon the following: ##EQU1##
Substituting for Y and Y' using equations [1] and [2] above yields: ##EQU2##
Therefore, Z=Z'
Thus, using the Diffie-Hellman protocol, A and B each possess the same secure key Z, Z' and can use it to encrypt messages to each other. An eavesdropper who intercepts an encrypted message can recover it only by knowing x or x', or by solving an extremely difficult discrete logarithm to yield x or x'. Thus, the Diffie-Hellman protocol provides a relatively secure approach.
A drawback of public key encryption approaches is that they require significant system resources and time to perform because they are computationally intensive. For example, performing the Diffie-Hellman approach requires performing both exponentiation and modulo computations which are known to require significant system resources and time. Depending on the application or environment in which the processing is occurring, the computing operations may create a processing bottleneck or unacceptable processing delays. Therefore, it is desirable to perform encryption/decryption operations as fast as possible.
Based upon the foregoing, there is a clear need for improved approaches to machine computation of values that have exponents, exponential functions, and modulo functions.
In particular, there is an acute need for an improved approach to machine computation of values that have exponents in which the approach uses as little machine memory as possible.
There is also a need for an improved approach to machine computation of values that involve modulo functions in which the approach does not use unnecessary processor divide instructions.
Further, there is a need for such approaches that avoid wasting machine operations or instructions on manipulating insignificant intermediate information that is created as part of the machine computation.
There is also a need for such approaches that prevent register overflow as an exponentiated value grows larger during the computation operations.
There is also a need for such approaches that minimize the number of memory allocation operations that are carried out during the approach.
Based on the need to provide secure communication while limiting the adverse effects on system resources and the limitations in the prior approaches, an approach for providing secure communication that provides a relatively high level of security while requiring relatively fewer system resources and time to perform is highly desirable.